import java.util.*;

public class Daily {
    public static void main(String[] args) {
        int[][] m = {{1, 2}, {4, 5}, {2, 3}};

        System.out.println(Arrays.deepToString(m));

        Arrays.sort(m, (int[] o1, int[] o2) -> o1[0] - o2[0]);

        System.out.println(Arrays.deepToString(m));

        Arrays.stream(m).map(Arrays::toString).forEach(System.out::println);

        String ss = "";
        List<Character> l = new ArrayList<Character>();
        l.add('a');
        l.add('b');
        l.add('c');
        String s = String.valueOf(l);
        PriorityQueue<Integer> p = new PriorityQueue<>(3, Collections.reverseOrder());
        p.add(1);
        p.add(2);
        p.add(3);
        p.add(4);
        p.add(4);
        p.add(4);
        p.add(4);

        p.contains(4);

        System.out.println(p.poll());
        System.out.println(p.poll());
        System.out.println(p.poll());
        System.out.println(p.poll());
        System.out.println(p.poll());

        List<Integer> ll = new ArrayList<>();
        ll.sort(new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return 0;
            }
        });
        int[] nums = new int[ll.size()];
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return nums[o1] - nums[o2];
            }
        });

        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);

    }

    /**
     * 下一个排列
     */
    public void nextPermutation(int[] nums) {
        int end = nums.length - 1, j = end;
        //  这里从后往前找打第一个升序数组j 表示的是升序数组的顶点
        for(; j >= 0; j--){
            if(j - 1 < 0) break;
            if(nums[j - 1] < nums[j]) break;
        }

        int k = end;
        // 找到第一个比j - 1 大的数
        for(; k >= j; k--){
            if(j - 1 >= 0 && nums[k] > nums[j - 1]){
                int tmp = nums[k];
                nums[k] = nums[j - 1];
                nums[j - 1] = tmp;
                break;
            }
        }

        //逆置j, n
        while(j < end){
            int tmp = nums[j];
            nums[j] = nums[end];
            nums[end] = tmp;
            j++; end--;
        }
    }

    /**
     * 零钱兑换
     */
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;

        int n = coins.length;

        //dp[i] 表示筹到i这个数额的硬币所需要的最少的硬币数
        //那么对于 dp[i] = min(dp[i - coins]) + 1; i >= coins
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);

        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < n; j++) {
                if (i >= coins[j]) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
    /**
     * 前 K 个高频元素
     */

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> stack = new PriorityQueue<>((o1, o2) -> map.getOrDefault(o2, 0) - map.getOrDefault(o1, 0));

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        for (int i : map.keySet()) {
            stack.add(i);
        }

        int[] ret = new int[k];
        int i = 0;
        while (!stack.isEmpty() && i != k) {
            ret[i++] = stack.poll();
        }
        System.out.println(map.get(0));

        return ret;
    }

    /**
     * 每日温度
     */

    public int[] dailyTemperatures(int[] t) {
        int n = t.length;
        //小根堆
        PriorityQueue<Integer> stack = new PriorityQueue<>((o1, o2) -> t[o1] - t[o2]);
        int[] ret = new int[n];
        stack.add(0);
        for (int i = 1; i < n; i++) {
            while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
                int peek = stack.peek();
                ret[peek] = i - peek > 0 ? i - peek : 0;
                stack.poll();
            }
            stack.add(i);
        }

        return ret;
    }

    /**
     * 分割等和子集
     */
    public boolean canPartition01(int[] nums) {
        // 0 1  背包
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }

        if (sum % 2 != 0) return false;

        int n = nums.length, t = sum / 2;
        //i 表示 0 - i 这个区间   j 表示体积  最终表示 0 - i这个区间是否有体积为 j 的子集
        boolean[][] dp = new boolean[n + 1][sum + 1];

        for (int i = 1; i <= n; i++) {
            int v = nums[i - 1];
            for (int j = 1; j <= t; j++) {
                //选
                if (j >= v) {
                    dp[i][j] = dp[i - 1][j - v];
                }
                //不选  又可能自己是满足条件的 不能忽略
                dp[i][j] = dp[i - 1][j] | dp[i][j] | j == v;
            }
        }

        return dp[n][t];
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }

        if (sum % 2 != 0) return false;
        int t = sum / 2;

        System.out.println(t);
        Set<Integer> set = new HashSet<Integer>();

        set.add(0);

        for (int i : nums) {
            int tmp = t - i;
            if (set.contains(tmp)) return true;
            //更新set中的值
            Set<Integer> set1 = new HashSet<Integer>(set);
            for (int v : set) {
                int v1 = i + v;
                if (v1 < t) {
                    set1.add(v1);
                }
            }
            set = set1;
        }

        return false;
    }

    // int path = 0;
    // boolean ret;
    // void dfs(int[] nums, int n, int t){
    //     if(n == nums.length){
    //         if(path == t) ret = true;
    //         return;
    //     }
    //     if(ret) return;

    //     //对于当前第n个元素 可以选择选或者不选
    //     //选
    //     path += nums[n];

    //     //减支
    //     if(path < t){
    //         dfs(nums, n + 1, t);
    //     }else if(path == t){
    //         ret = true;
    //     }
    //     path -= nums[n];

    //     //只需要找到一条就行
    //     if(ret) return;

    //     //不选
    //     dfs(nums, n + 1, t);
    // }

    /**
     * 和为 K 的子数组
     */

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0; //所有元素前缀和
        int ret = 0;
        for (int i : nums) {
            sum += i;
            //map 中的是之前元素的前缀和
            ret += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }

    /**
     * 无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String ss) {
        Map<Character, Integer> map = new HashMap<>();
        int r = 0, l = 0, n = ss.length();
        char[] s = ss.toCharArray();
        int max = 0;
        while (r < n && l <= r) {
            char c = s[r];
            //判断窗口中是否存在这个字符
            if (!map.containsKey(c)) {
                //不存在
                map.put(c, r++);
            } else {
                //存在
                max = Math.max(r - l, max);
                //l  走到这这个字符的下一个位置
                int i = map.get(c);
                //说明没有用了 这个元素已经出窗口了
                if (i < l) {
                    map.remove(c);
                    continue;
                }
                l = i + 1;
                map.remove(c);
            }
        }
        max = Math.max(r - l, max);
        return max;
    }

    /**
     * 分割链表
     */
    //有内存限制 原地修改了
    public ListNode partition(ListNode head, int x) {
        ListNode l = head; //这个表示从这个位置开始向前的都小于等于x的 那么l就需要走到大于x的位置
        ListNode r = head; //cur遍历整个数组 找到小于x的 将他和l交换 这样l之后的肯定时小于等于x的

        while (r != null) {
            //找到l大等于x的位置
            while (l != null && l.val < x) {
                l = l.next;
            }

            //从这里向后找找到比x小的位置
            if (l == null) break;
            r = l.next;

            while (r != null && r.val >= x) {
                r = r.next;
            }

            if (r == null) break;
            swap(l, r);
        }

        return head;
    }

    void swap(ListNode l, ListNode r) {
        int tmp = l.val;
        l.val = r.val;
        r.val = tmp;
    }

    /**
     * 破冰游戏 约瑟夫环
     */
    public int iceBreakingGame(int num, int target) {
        // 动态规划 num 代表的是 大小未num的环
        // 而这个 num大小的环 取决于 （num - 1） 这个环最终剩余的位置再走 target步
        // 所以 有 i =  (i - 1 + target) % x 这个公式 来表示 大小为x的环的最后一个元素
        int x = 0;
        for (int i = 2; i <= num; i++) { //i表示环大小
            x = (x + target) % i;
        }
        return x;
    }

    /**
     * 将 x 减到 0 的最小操作数
     */
    //找到数组中满足的最大的窗口 sum - x ，没有就放回 -1
    public int minOperations(int[] nums, int x) {
        int sum = 0;
        for (int i : nums) sum += i;

        int l = 0, r = 0;
        int window = 0, max = 0;
        int target = sum - x;
        if (target == 0) return nums.length;
        if (target < 0) return -1;
        while (r < nums.length) {
            //如窗口
            window += nums[r];

            while (l <= r && window >= target) {
                if (window == target) {
                    max = Math.max(max, r - l + 1);
                }
                window -= nums[l++];
            }
            r++;
        }
        if (max == 0) return -1;
        return nums.length - max;
    }

    /**
     * 全排列II
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> ret = new ArrayList<>();
        boolean[] check = new boolean[n];
        Arrays.sort(nums);
        dfs(n, nums, check, path, ret);
        return ret;
    }

    void dfs(int n, int[] nums, boolean[] check, List<Integer> path, List<List<Integer>> ret) {
        if (path.size() == n) {
            ret.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (check[i] || (i - 1 >= 0 && nums[i - 1] == nums[i] && !check[i - 1])) continue;

            path.add(nums[i]);
            check[i] = true;

            dfs(n, nums, check, path, ret);

            check[i] = false;
            path.remove(path.size() - 1);

        }
    }

    /**
     * 成最多水的容器
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        //双指针
        int r = height.length - 1, l = 0;
        int max = 0;
        while (r > l) {
            max = Math.max((r - l) * Math.min(height[l], height[r]), max);
            if (height[l] > height[r]) r--;
            else l++;
        }
        return max;
    }

    /**
     * 覆盖子字符串
     */
    Map<Character, Integer> tMap = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    public String minWindow(String ss, String tt) {
        for (char c : tt.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        char[] s = ss.toCharArray();

        int n = s.length;

        int l = 0, r = 0;
        int min = Integer.MAX_VALUE, rl = -1, rr = -1;
        for (; r < n; r++) {
            //入窗口
            if (tMap.containsKey(s[r])) {
                window.put(s[r], window.getOrDefault(s[r], 0) + 1);
            }
            //出窗口 r此时对应的就tMap中的一元素 如果window中包含了所有的字母
            while (check() && l <= r) {
                if (r - l < min) {
                    min = r - l;
                    rr = r + 1;
                    rl = l;
                }
                if (window.containsKey(s[l])) {
                    window.put(s[l], window.get(s[l]) - 1);
                }
                l++;
            }
        }
        if (rl == -1) return "";
        return ss.substring(rl, rr);
    }

    boolean check() {
        Set<Character> s = tMap.keySet();
        for (Character c : s) {
            int t1 = tMap.get(c);
            int t2 = window.getOrDefault(c, 0);
            //如果不完全包含tmap中的字符 就不出窗口
            if (t1 > t2) return false;
        }
        return true;
    }

    /**
     * 水果成篮 滑动窗口
     * 滑动窗口 每次出窗口出的是一个水果的种类
     */
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int max = 0;
        //用这俩个来代表水果 和数量
        int a = -1, al = 0;
        int b = -1, bl = 0;
        int l = 0, r = 0;
        for (; r < n; ) {
            //入窗口 有一种水果为种类为-1
            if (a == -1 || b == -1 || fruits[r] == a || fruits[r] == b) {
                if (a == -1 || fruits[r] == a) {
                    a = fruits[r];
                    al++;
                } else {
                    b = fruits[r];
                    bl++;
                }
                r++;
            } else {//出窗口
                max = Math.max(max, al + bl);
                //其中有一个为-1 就完成了一种水果的出窗口
                while (a != -1 && b != -1) {
                    if (fruits[l] == a) {
                        al--;
                        if (al == 0) {
                            a = -1;
                        }
                    } else {
                        bl--;
                        if (bl == 0) {
                            b = -1;
                        }
                    }
                    l++;
                }
            }
        }
        max = Math.max(max, al + bl);
        return max;
    }
}
